home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1996 #15 / Monster Media Number 15 (Monster Media)(July 1996).ISO / math / differ.zip / SIMPLIFY.C < prev   
C/C++ Source or Header  |  1996-02-11  |  17KB  |  582 lines
  1. #include "differ.h"
  2.  
  3. /*
  4.    This is a recursive routine to check two expressions for equality.
  5.    Its useful in simplifying.
  6. */
  7.  
  8. logical equaltrees(struct expression *tree1,struct expression *tree2)
  9. { if((tree1==NULL)&&(tree2==NULL)) return TRUE;
  10.   if(tree1==NULL) return FALSE;
  11.   if(tree2==NULL) return FALSE;
  12.   if(tree1->exptype==tree2->exptype)
  13.   { switch(tree1->exptype)
  14.     { case OPERATOR:if(tree1->expval.op==tree2->expval.op)
  15.                 return ((equaltrees(tree1->lval,tree2->lval))&(equaltrees(tree1->rval,tree2->rval)));
  16.               else return FALSE;
  17.     case FUNCTION:if(tree1->expval.fn==tree2->expval.fn)
  18.                 return (equaltrees(tree1->rval,tree2->rval));
  19.               else return FALSE;
  20.     case X:       return TRUE;
  21.     case VALUE:   if(tree1->cval==tree2->cval) return TRUE;
  22.               else return FALSE;
  23.     case CONSTANT:if(tree1->expval.co==tree2->expval.co)
  24.                 return TRUE;
  25.               else return FALSE;
  26.     default:      return FALSE;
  27.     }
  28.   }
  29.   return FALSE;
  30. }
  31.  
  32. /*
  33.    Heres the simplify routine.
  34.    Some simplifications are quite easy like
  35.      u * 1 = u
  36.      u * 0 = 0
  37.    Others are more complicated like moving unitary minuses up the tree.
  38.    If you alter this then be careful. The routine is highly recursive
  39.    and its easy to create recursive loops where simplifications are
  40.    working against each other.
  41.    Its also questionable in some circumstances whether you want to make
  42.    a change. For example consider
  43.      3*(x+1)
  44.    Do you want to change this to
  45.      3*x+3
  46.    because if you do then you might find cases where the output is
  47.      (3*x+3)/(x+1) say
  48.    whereas before it was
  49.      3
  50.    because the x+1's cancelled.
  51.    On the other hand if you look at the examples carefully, one gives an
  52.    output which contains
  53.      7*(7*x+1)+7*(7*x-1)
  54.    Here this should more easily be
  55.      98*x
  56.    but how do you get to this and still provide for all the other cases ?
  57.    I leave it to you to decide.
  58.  
  59.    One other thing, I've done some manipulations with the pointers in
  60.    manipulating expressions, so change things carefully.
  61. */
  62.  
  63. struct expression *simplify(struct expression *expr)
  64. { struct expression *lv,
  65.               *rv;
  66.   if(expr==NULL) return NULL;
  67.   expr->lval=simplify(expr->lval);
  68.   expr->rval=simplify(expr->rval);
  69.   if (expr->exptype==VALUE)
  70.   { if (expr->cval<0)
  71.     { expr->cval=-expr->cval;
  72.     lv=newtree();
  73.     lv->exptype=OPERATOR;
  74.     lv->expval.op=UMINUS;
  75.     lv->rval=expr;
  76.     return lv;
  77.     }
  78.   }
  79.   if (expr->exptype==OPERATOR)
  80.   { lv=expr->lval;
  81.     rv=expr->rval;
  82.     switch(expr->expval.op)
  83.     { case TIMES:      if((rv->exptype==OPERATOR)&&((rv->expval.op==TIMES)||(rv->expval.op==DIVIDE)))
  84.                  { while((rv->exptype==OPERATOR)&&(rv->expval.op==TIMES))
  85.                    rv=rv->rval;
  86.                  if((rv->exptype==OPERATOR)&&(rv->expval.op==DIVIDE))
  87.                  { if(equaltrees(rv->rval,lv))
  88.                    { lv=expr->rval;
  89.                      expr->rval=NULL;
  90.                      freetree(expr);
  91.                      freetree(rv->rval);
  92.                      expr=lv;
  93.                      lv=newtree();
  94.                      lv->exptype=VALUE;
  95.                      lv->cval=1;
  96.                      rv->rval=lv;
  97.                      return simplify(expr);
  98.                    }
  99.                  }
  100.                  rv=expr->rval;
  101.                  }
  102.                  if((lv->exptype==OPERATOR)&&(lv->expval.op==TIMES))
  103.                  { expr->lval=lv->rval;
  104.                  lv->rval=expr;
  105.                  return simplify(lv);
  106.                  }
  107.                  else if(((rv->exptype)<(lv->exptype))&&(((lv->exptype)<OPERATOR)
  108.                  ||((lv->exptype==OPERATOR)&&(rv->exptype==VALUE))))
  109.                  { expr->lval=rv;
  110.                  expr->rval=lv;
  111.                  lv=expr->lval;
  112.                  rv=expr->rval;
  113.                  return simplify(expr);
  114.                  }
  115.                  if((rv->exptype==OPERATOR)&&((rv->expval.op==TIMES)||(rv->expval.op==DIVIDE)))
  116.                  { if((lv->exptype)>(rv->lval->exptype))
  117.                  { expr->lval=rv->lval;
  118.                    rv->lval=lv;
  119.                    lv=expr->lval;
  120.                    return simplify(expr);
  121.                  }
  122.                  }
  123.                  if((lv->exptype==VALUE)&&(lv->cval==1))
  124.                  { expr->rval=NULL;
  125.                  freetree(expr);
  126.                  return simplify(rv);
  127.                  }
  128.                  if((lv->exptype==VALUE)&&(lv->cval==-1))
  129.                  { expr->lval=NULL;
  130.                  freetree(lv);
  131.                  expr->expval.op=UMINUS;
  132.                  return simplify(expr);
  133.                  }
  134.                  if((rv->exptype==VALUE)&&(rv->cval==1))
  135.                  { expr->lval=NULL;
  136.                  freetree(expr);
  137.                  return simplify(lv);
  138.                  }
  139.                  if((lv->exptype==VALUE)&&(lv->cval==0))
  140.                  { expr->lval=NULL;
  141.                  freetree(expr);
  142.                  return lv;
  143.                  }
  144.                  if((rv->exptype==VALUE)&&(rv->cval==0))
  145.                  { expr->rval=NULL;
  146.                  freetree(expr);
  147.                  return rv;
  148.                  }
  149.                  if((lv->exptype==VALUE)&&(rv->exptype==VALUE))
  150.                  { lv->cval*=rv->cval;
  151.                  expr->lval=NULL;
  152.                  freetree(expr);
  153.                  return simplify(lv);
  154.                  }
  155.                  if((lv->exptype==VALUE)&&(rv->exptype==OPERATOR))
  156.                  { if((rv->expval.op==TIMES)&&(rv->lval->exptype==VALUE))
  157.                  { rv->lval->cval*=lv->cval;
  158.                    expr->rval=NULL;
  159.                    freetree(expr);
  160.                    return simplify(rv);
  161.                  }
  162.                  }
  163.                  if(equaltrees(lv,rv))
  164.                  { expr->lval=NULL;
  165.                  freetree(expr);
  166.                  expr=newtree();
  167.                  rv=newtree();
  168.                  expr->exptype=OPERATOR;
  169.                  expr->expval.op=POWER;
  170.                  expr->lval=lv;
  171.                  expr->rval=rv;
  172.                  rv->exptype=VALUE;
  173.                  rv->cval=2;
  174.                  return simplify(expr);
  175.                  }
  176.                  if((lv->exptype==OPERATOR)&&(rv->exptype==OPERATOR))
  177.                  { if((lv->expval.op==DIVIDE)&&(rv->expval.op==POWER))
  178.                    if(equaltrees(lv->rval,rv->lval))
  179.                    { lv=lv->lval;
  180.                      expr->lval->lval=NULL;
  181.                      freetree(expr->lval);
  182.                      expr->lval=lv;
  183.                      rv=newtree();
  184.                      rv->exptype=OPERATOR;
  185.                      rv->expval.op=MINUS;
  186.                      rv->lval=expr->rval->rval;
  187.                      expr->rval->rval=rv;
  188.                      rv=newtree();
  189.                      rv->exptype=VALUE;
  190.                      rv->cval=1;
  191.                      expr->rval->rval->rval=rv;
  192.                      return simplify(expr);
  193.                    }
  194.                  else
  195.                  if((lv->expval.op==TIMES)&&(rv->expval.op==POWER))
  196.                    if(equaltrees(lv->rval,rv->lval))
  197.                    { lv=lv->lval;
  198.                      expr->lval->lval=NULL;
  199.                      freetree(expr->lval);
  200.                      expr->lval=lv;
  201.                      rv=newtree();
  202.                      rv->exptype=OPERATOR;
  203.                      rv->expval.op=PLUS;
  204.                      rv->lval=expr->rval->rval;
  205.                      expr->rval->rval=rv;
  206.                      rv=newtree();
  207.                      rv->exptype=VALUE;
  208.                      rv->cval=1;
  209.                      expr->rval->rval->rval=rv;
  210.                      return simplify(expr);
  211.                    }
  212.                  }
  213.                  if(rv->exptype==OPERATOR)
  214.                  { if(rv->expval.op==POWER)
  215.                  { if(equaltrees(lv,rv->lval))
  216.                    { expr->rval=NULL;
  217.                      freetree(expr);
  218.                      expr=rv;
  219.                      rv=newtree();
  220.                      rv->exptype=OPERATOR;
  221.                      rv->expval.op=PLUS;
  222.                      rv->lval=expr->rval;
  223.                      expr->rval=rv;
  224.                      rv=newtree();
  225.                      rv->exptype=VALUE;
  226.                      rv->cval=1;
  227.                      expr->rval->rval=rv;
  228.                      return simplify(expr);
  229.                    }
  230.                    else
  231.                    if((rv->rval->exptype==VALUE)&&(rv->rval->cval<0))
  232.                    { expr->expval.op=DIVIDE;
  233.                      rv->rval->cval=-rv->rval->cval;
  234.                      return simplify(expr);
  235.                    }
  236.                    else
  237.                    if((rv->rval->exptype==OPERATOR)&&(rv->rval->expval.op==UMINUS))
  238.                    { expr->expval.op=DIVIDE;
  239.                      rv=rv->rval->rval;
  240.                      expr->rval->rval->rval=NULL;
  241.                      freetree(expr->rval->rval);
  242.                      expr->rval->rval=rv;
  243.                      return simplify(expr);
  244.                    }
  245.                  }
  246.                  else
  247.                  if(rv->expval.op==UMINUS)
  248.                  { expr->rval=expr->rval->rval;
  249.                    rv->rval=expr;
  250.                    return simplify(rv);
  251.                  }
  252.                  else
  253.                  if((rv->expval.op==TIMES)||(rv->expval.op==DIVIDE))
  254.                  { if(equaltrees(lv,rv->lval))
  255.                    { expr->rval=NULL;
  256.                      freetree(expr);
  257.                      expr=rv;
  258.                      lv=newtree();
  259.                      lv->exptype=OPERATOR;
  260.                      lv->expval.op=POWER;
  261.                      lv->lval=expr->lval;
  262.                      expr->lval=lv;
  263.                      lv=newtree();
  264.                      lv->exptype=VALUE;
  265.                      lv->cval=2;
  266.                      expr->lval->rval=lv;
  267.                      return simplify(expr);
  268.                    }
  269.                  }
  270.                  }
  271.                  if(lv->exptype==OPERATOR)
  272.                  { if(lv->expval.op==POWER)
  273.                  { if(equaltrees(lv->lval,rv))
  274.                    { expr->lval=NULL;
  275.                      freetree(expr);
  276.                      expr=lv;
  277.                      lv=newtree();
  278.                      lv->exptype=OPERATOR;
  279.                      lv->expval.op=PLUS;
  280.                      lv->lval=expr->rval;
  281.                      expr->rval=lv;
  282.                      rv=newtree();
  283.                      rv->exptype=VALUE;
  284.                      rv->cval=1;
  285.                      expr->rval->rval=rv;
  286.                      return simplify(expr);
  287.                    }
  288.                  }
  289.                  else
  290.                  if(lv->expval.op==UMINUS)
  291.                  { expr->lval=expr->lval->rval;
  292.                    lv->rval=expr;
  293.                    return simplify(lv);
  294.                  }
  295.                  }
  296.                  if((lv->exptype==OPERATOR)&&(lv->expval.op==POWER)&&
  297.                   (rv->exptype==OPERATOR)&&(rv->expval.op==POWER))
  298.                  if(equaltrees(lv->lval,rv->lval))
  299.                  { lv=newtree();
  300.                    lv->exptype=OPERATOR;
  301.                    lv->expval.op=PLUS;
  302.                    lv->rval=rv->rval;
  303.                    lv->lval=expr->lval->rval;
  304.                    rv->rval=lv;
  305.                    expr->lval->rval=NULL;
  306.                    expr->rval=NULL;
  307.                    freetree(expr);
  308.                    return simplify(rv);
  309.                  }
  310.                  break;
  311.     case PLUS:       if((lv->exptype==OPERATOR)&&(lv->expval.op==PLUS))
  312.                  { expr->lval=lv->rval;
  313.                  lv->rval=expr;
  314.                  return simplify(lv);
  315.                  }
  316.                  if((rv->exptype==OPERATOR)&&(rv->expval.op==PLUS))
  317.                  { if((lv->exptype)<(rv->lval->exptype))
  318.                  { expr->lval=rv->lval;
  319.                    rv->lval=lv;
  320.                    lv=expr->lval;
  321.                    return simplify(expr);
  322.                  }
  323.                  }
  324.                  if((lv->exptype==VALUE)&&(lv->cval==0))
  325.                  { expr->rval=NULL;
  326.                  freetree(expr);
  327.                  return rv;
  328.                  }
  329.                  if((rv->exptype==VALUE)&&(rv->cval==0))
  330.                  { expr->lval=NULL;
  331.                  freetree(expr);
  332.                  return lv;
  333.                  }
  334.                  if((lv->exptype==VALUE)&&(rv->exptype==VALUE))
  335.                  { lv->cval+=rv->cval;
  336.                  expr->lval=NULL;
  337.                  freetree(expr);
  338.                  return lv;
  339.                  }
  340.                  if((rv->exptype==VALUE)&&(rv->cval<0))
  341.                  { expr->exptype=MINUS;
  342.                  rv->cval=-rv->cval;
  343.                  return expr;
  344.                  }
  345.                  if((rv->exptype==OPERATOR)&&(rv->expval.op==UMINUS))
  346.                  { expr->expval.op=MINUS;
  347.                  expr->rval=expr->rval->rval;
  348.                  rv->rval=NULL;
  349.                  freetree(rv);
  350.                  return simplify(expr);
  351.                  }
  352.                  break;
  353.     case MINUS:      if((lv->exptype==VALUE)&&(rv->exptype==VALUE))
  354.                  { lv->cval-=rv->cval;
  355.                  expr->lval=NULL;
  356.                  freetree(expr);
  357.                  return simplify(lv);
  358.                  }
  359.                  if((lv->exptype==VALUE)&&(lv->cval==0))
  360.                  { expr->lval=NULL;
  361.                  expr->expval.op=UMINUS;
  362.                  freetree(lv);
  363.                  return simplify(expr);
  364.                  }
  365.                  if((rv->exptype==VALUE)&&(rv->cval==0))
  366.                  { expr->lval=NULL;
  367.                  freetree(expr);
  368.                  return lv;
  369.                  }
  370.                  if((rv->exptype==VALUE)&&(rv->cval<0))
  371.                  { expr->exptype=PLUS;
  372.                  rv->cval=-rv->cval;
  373.                  return expr;
  374.                  }
  375.                  if((rv->exptype==OPERATOR)&&(rv->expval.op==UMINUS))
  376.                  { expr->expval.op=PLUS;
  377.                  expr->rval=expr->rval->rval;
  378.                  rv->rval=NULL;
  379.                  freetree(rv);
  380.                  return simplify(expr);
  381.                  }
  382.                  if((lv->exptype==OPERATOR)&&(lv->expval.op==UMINUS))
  383.                  { expr->expval.op=PLUS;
  384.                  expr->lval=lv->rval;
  385.                  lv->rval=expr;
  386.                  return simplify(lv);
  387.                  }
  388.                  if((rv->exptype==OPERATOR)&&(rv->expval.op==MINUS))
  389.                  { expr->expval.op=PLUS;
  390.                  expr->lval=expr->rval->rval;
  391.                  expr->rval->rval=expr->rval->lval;
  392.                  expr->rval->lval=lv;
  393.                  return simplify(expr);
  394.                  }
  395.                  break;
  396.     case UMINUS:     if((rv->exptype==VALUE)&&(rv->cval<=0))
  397.                  { rv->cval=-rv->cval;
  398.                  expr->rval=NULL;
  399.                  freetree(expr);
  400.                  return rv;
  401.                  }
  402.                  if((rv->exptype==OPERATOR)&&(rv->expval.op==UMINUS))
  403.                  { rv=rv->rval;
  404.                  expr->rval->rval=NULL;
  405.                  freetree(expr);
  406.                  return rv;
  407.                  }
  408.                  break;
  409.     case DIVIDE:     if((rv->exptype==OPERATOR)&&(rv->expval.op==TIMES))
  410.                  { while((rv->exptype==OPERATOR)&&(rv->expval.op==TIMES))
  411.                  { if(equaltrees(rv->lval,lv))
  412.                    { freetree(lv);
  413.                      lv=newtree();
  414.                      lv->exptype=VALUE;
  415.                      lv->cval=1;
  416.                      expr->lval=lv;
  417.                      freetree(rv->lval);
  418.                      lv=newtree();
  419.                      lv->exptype=VALUE;
  420.                      lv->cval=1;
  421.                      rv->lval=lv;
  422.                      return simplify(expr);
  423.                    }
  424.                    if(equaltrees(rv->rval,lv))
  425.                    { freetree(lv);
  426.                      lv=newtree();
  427.                      lv->exptype=VALUE;
  428.                      lv->cval=1;
  429.                      expr->lval=lv;
  430.                      freetree(rv->rval);
  431.                      lv=newtree();
  432.                      lv->exptype=VALUE;
  433.                      lv->cval=1;
  434.                      rv->rval=lv;
  435.                      return simplify(expr);
  436.                    }
  437.                    rv=rv->rval;
  438.                  }
  439.                  rv=expr->rval;
  440.                  }
  441.                  if((lv->exptype==VALUE)&&(rv->exptype==VALUE))
  442.                  { lv->cval/=rv->cval;
  443.                  expr->lval=NULL;
  444.                  freetree(expr);
  445.                  return lv;
  446.                  }
  447.                  if(rv->exptype==VALUE)
  448.                  { expr->expval.op=TIMES;
  449.                  rv->cval=1/rv->cval;
  450.                  return simplify(expr);
  451.                  }
  452.                  if(equaltrees(lv,rv))
  453.                  { freetree(expr);
  454.                  expr=newtree();
  455.                  expr->exptype=VALUE;
  456.                  expr->cval=1;
  457.                  return expr;
  458.                  }
  459.                  if((lv->exptype==OPERATOR)&&(lv->expval.op==TIMES))
  460.                  { expr->expval.op=TIMES;
  461.                  expr->rval=lv;
  462.                  expr->rval->expval.op=DIVIDE;
  463.                  expr->lval=expr->rval->lval;
  464.                  expr->rval->lval=expr->rval->rval;
  465.                  expr->rval->rval=rv;
  466.                  return simplify(expr);
  467.                  }
  468.                  if((lv->exptype==OPERATOR)&&(lv->expval.op==DIVIDE))
  469.                  { lv->expval.op=TIMES;
  470.                  expr->rval=lv;
  471.                  expr->lval=expr->rval->lval;
  472.                  expr->rval->lval=expr->rval->rval;
  473.                  expr->rval->rval=rv;
  474.                  return simplify(expr);
  475.                  }
  476.                  if((rv->exptype==OPERATOR)&&(rv->expval.op==DIVIDE))
  477.                  { expr->expval.op=TIMES;
  478.                  rv=rv->rval;
  479.                  expr->rval->rval=expr->rval->lval;
  480.                  expr->rval->lval=rv;
  481.                  return simplify(expr);
  482.                  }
  483.                  if((rv->exptype==OPERATOR)&&(rv->expval.op==POWER))
  484.                  if(!((rv->rval->exptype==VALUE)&&(rv->rval->cval>=0)))
  485.                  { expr->expval.op=TIMES;
  486.                    rv=newtree();
  487.                    rv->exptype=OPERATOR;
  488.                    rv->expval.op=UMINUS;
  489.                    rv->rval=expr->rval->rval;
  490.                    expr->rval->rval=rv;
  491.                    return simplify(expr);
  492.                  }
  493.                  else
  494.                  if(equaltrees(lv,rv->lval))
  495.                  { expr->rval=NULL;
  496.                    freetree(expr);
  497.                    lv=newtree();
  498.                    lv->exptype=OPERATOR;
  499.                    lv->expval.op=MINUS;
  500.                    lv->rval=rv->rval;
  501.                    rv->rval=lv;
  502.                    lv=newtree();
  503.                    lv->exptype=VALUE;
  504.                    lv->cval=1;
  505.                    rv->rval->lval=lv;
  506.                    return simplify(rv);
  507.                  }
  508.                  if((lv->exptype==OPERATOR)&&(lv->expval.op==POWER))
  509.                  if(equaltrees(lv->lval,rv))
  510.                  { expr->lval=NULL;
  511.                    freetree(expr);
  512.                    rv=newtree();
  513.                    rv->exptype=OPERATOR;
  514.                    rv->expval.op=MINUS;
  515.                    rv->lval=lv->rval;
  516.                    lv->rval=rv;
  517.                    rv=newtree();
  518.                    rv->exptype=VALUE;
  519.                    rv->cval=1;
  520.                    lv->rval->rval=rv;
  521.                    return simplify(lv);
  522.                  }
  523.                  if((lv->exptype==OPERATOR)&&(lv->expval.op==UMINUS))
  524.                  { expr->lval=lv->rval;
  525.                  lv->rval=expr;
  526.                  return simplify(lv);
  527.                  }
  528.                  if((rv->exptype==OPERATOR)&&(rv->expval.op==UMINUS))
  529.                  { expr->rval=rv->rval;
  530.                  rv->rval=expr;
  531.                  return simplify(rv);
  532.                  }
  533.                  if((lv->exptype==OPERATOR)&&(lv->expval.op==POWER)&&
  534.                   (rv->exptype==OPERATOR)&&(rv->expval.op==POWER))
  535.                  if(equaltrees(lv->lval,rv->lval))
  536.                  { lv=newtree();
  537.                    lv->exptype=OPERATOR;
  538.                    lv->expval.op=MINUS;
  539.                    lv->rval=rv->rval;
  540.                    lv->lval=expr->lval->rval;
  541.                    rv->rval=lv;
  542.                    expr->lval->rval=NULL;
  543.                    expr->rval=NULL;
  544.                    freetree(expr);
  545.                    return simplify(rv);
  546.                  }
  547.                  break;
  548.     case POWER:      if((rv->exptype==VALUE)&&(rv->cval==1))
  549.                  { expr->lval=NULL;
  550.                  freetree(expr);
  551.                  return lv;
  552.                  }
  553.                  if((lv->exptype==OPERATOR)&&(lv->expval.op==POWER))
  554.                  if((lv->rval->exptype==VALUE)&&(rv->exptype==VALUE))
  555.                  { lv->rval->cval*=rv->cval;
  556.                    expr->lval=NULL;
  557.                    freetree(expr);
  558.                    return lv;
  559.                  }
  560.                  if((lv->exptype==OPERATOR)&&(lv->expval.op==UMINUS))
  561.                  if((rv->exptype==VALUE))
  562.                  { if((float)((int)(rv->cval/2))==(rv->cval/2))
  563.                    { expr->lval=expr->lval->rval;
  564.                      lv->rval=NULL;
  565.                      freetree(lv);
  566.                      return simplify(expr);
  567.                    }
  568.                    else
  569.                    if((float)((int)((rv->cval-1)/2))==((rv->cval-1)/2))
  570.                    { expr->lval=expr->lval->rval;
  571.                      lv->rval=expr;
  572.                      return simplify(lv);
  573.                    }
  574.                  }
  575.                  break;
  576.     case UNDEF_OP:
  577.     default:         break;
  578.     }
  579.   }
  580.   return expr;
  581. }
  582.